package ljl.alg.wangzheng_camp.round1.tree;

import commons.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class _106_make_tree_in_post {
    
    /**
     * 照葫芦画瓢，画出来了
     * */
    class ok {
        
        Map<Integer, Integer> inMap = new HashMap<>();
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int n = inorder.length;
            for (int i = 0; i < n; i++) {
                inMap.put(inorder[i], i);
            }
            return make(inorder, 0, n - 1, postorder, 0, n - 1);
        }
        TreeNode make(int[] in, int inl, int inr, int[] post, int pl, int pr) {
            if (inl > inr) return null;
            TreeNode root = new TreeNode(post[pr]);
            int llen = inMap.get(post[pr]) - inl;
        
            root.left = make(in, inl, inl + llen - 1, post, pl, pl + llen - 1);
            root.right = make(in, inl + llen + 1, inr, post, pl + llen, pr - 1);
            return root;
        }
    }
    
    /**
     * 官方题解出了一个很简洁的解法
     * 虽然参数更少了，但是更难理解了
     *
     * */
    class of1 {
        Map<Integer, Integer> inMap = new HashMap<>();
        int[] in;
        int[] post;
        int postIndex;
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int n = inorder.length;
            postIndex = n - 1;
            in = inorder;
            post = postorder;
            int i = 0;
            for (int val : inorder) {
                inMap.put(val, i++);
            }
            return make(0, n - 1);
        }
        TreeNode make(int l, int r) {
            if (l > r) return null;
            TreeNode root = new TreeNode(post[postIndex]);
            int rootIndexInInorder = inMap.get(post[postIndex]);
            postIndex--;
            root.right = make(rootIndexInInorder + 1, r);
            root.left = make(l, rootIndexInInorder - 1);
            return root;
        }
    }
    
    /**
     * 没敢自己想，还是直接看的答案
     * */
    class of2 {
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            int n = postorder.length;
            LinkedList<TreeNode> stack = new LinkedList<>();
            TreeNode root;
            stack.push(root = new TreeNode(postorder[n - 1]));
            int inorderIndex = n - 1;
            for (int i = n - 2; i >= 0; i--) {
                int postVal = postorder[i];
                TreeNode node = stack.peek();
                if (node.val != inorder[inorderIndex]) {
                    node.right = new TreeNode(postVal);
                    stack.push(node.right);
                } else {
                    while (!stack.isEmpty() && inorder[inorderIndex] == stack.peek().val) {
                        node = stack.pop();
                        inorderIndex--;
                    }
                    node.left = new TreeNode(postVal);
                    stack.push(node.left);
                }
            }
            return root;
        }
    }
    
}
